perm filename SMLBK1.PAL[HAL,HE] blob sn#155557 filedate 1975-04-24 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.SBTTL Small block allocator:  GTITEM
C00009 ENDMK
C⊗;
.SBTTL Small block allocator:  GTITEM
;Coded by RF, 10-Sept-1974

;For small items like value cells, typically ranging in size
;from 1 to 20 words, many of which are needed, there is a 
;small block allocator.  Sixteen items of like size are
;allocated simultaneously with GTFREE when needed.  SZHH points
;to a the size header for the smallest size currently being
;used.  (One efficiency not currently programmed in is
;to have this initially point to a size header for an impossible
;large size item.)  Each size has its own header, pointing
;down a list of small blocks which have been allocated for this
;size.  Each block holds the 16 items.

;Global, pointing to smallest size header.
SZHH:	.BLKW 1		;Size header Header.

;Size header.  Each small block size has one of these.
	II == 0
	XX  NXTSH	;Next size header, for bigger blocks. (Must be first field)
	XX  SIZE	;Size of item in small block in WORDS.
	XX  NALLOC	;Number of allocated blocks.
	XX  BLKLST	;Points to first small block of this size.
	SIZSH = II/2	;How long a size header is in WORDS.

;Small block.  Each one holds 16 items, as well as this info:
	II == 0
	XX  NEXTB	;Next block of this size. (Must be first field)
	XX  MASK	;Each bit for one item.  0=free; 1=busy.
	XX  FRBIT	;Rotating bit.  Points to last assigned place.
	XX  WORD0	;First word of 16*SIZE words.
	SIZBLH = II/2	;How long a block header is in WORDS.

;Routine to allocate an item of size R0 words.  Returns location
;	of item found in R0.
GTITEM:	MOV R2,-(SP)	;Save R2.
	MOV R3,-(SP)	;Save R3.
	MOV #SZHH,R3	;R3 ← LOC[SZHH].  Used to link in new.
	MOV NXTSH(r3),R1	;R1 ← LOC[first size header]
	BEQ GTNWSH	;If 0, then need new size header.
GT1:	MOV SIZE(R1),R2	;R2 ← size of current size header in words.
	CMP R2,R0	;Is this the size we want?
	BEQ GTSZFD	;Yes.  We found the size.
	BGT GTNWSH	;No, too large.  Need new size header.
	MOV R1,R3	;No, too small. R3 ← LOC[too small size header]
	MOV NXTSH(R1),R1 ;R1 ← LOC[next size header]
	BNE GT1		;If there is one, try again.
GTNWSH:	MOV R0,-(SP)	;Save R0.
	MOV R1,-(SP)	;Save R1.
	MOV #SIZSH,R0	;R0 ← Number of words needed for a size header.
	JSR PC,GTFREE	;Get a block of that size.
	MOV R0,R1	;R1 ← LOC[new size header]
	MOV (SP)+,NXTSH(R1) ;NXTSH[new size header] ← LOC[next size header]
	MOV R1,NXTSH(R3);NXTSH[previous size header] ← LOC[new size header]
	MOV (SP)+,R0	;Restore R0 ← size desired in words.
	MOV R0,SIZE(R1)	;SIZE[new size header] ← correct size
	CLR NALLOC(R1)	;NALLOC[new size header] ← 0
	CLR BLKLST(R1)	;BLKLST[new size header] ← 0
;At this point, we have found a size header of the right size.
;R0 = size, R1 = LOC[size header found]
GTSZFD:	ROL R0		;R0 ← desired size in BYTES.
	MOV BLKLST(R1),R3;R3 ← LOC[block to try]
	BEQ GTNWBL	;If no more blocks, then get a new one.
GT5:	CMP #-1,MASK(R3);Is this block full?
	BNE GDBLK	;No.  Can use it.
	MOV NEXTB(R3),R3;Yes.  Get another block.
	BNE GT5		;If there is one, try it.
GTNWBL:	ROL R0		;Else need new block.
	ROL R0		;Recall:  R0 = 2*SIZE (since in bytes)
	ROL R0		;R0 ← 20*SIZE words
	ADD #SIZBLH,R0	;R0 ← Size of block we need.
	MOV R1,R2	;R1 will be clobbered soon.  R2 ← LOC[size header].
	JSR PC,GTFREE	;R0 ← LOC[new block]
	MOV BLKLST(R2),NEXTB(R0);NEXTB[block just made] ← LOC[first old block]
	MOV R0,BLKLST(R2);BLKLST[size header] ← LOC[block just made]
	INC NALLOC(R2)	;Just allocated a new block.
	MOV #100000,FRBIT(R0);Set its FRBIT arbitrarily.
	MOV FRBIT(R0),MASK(R0);We will assign this item to caller.
	ADD #WORD0,R0	;R0 ← LOC[new item]
	BR  GTRET	;Prepare to return.
GDBLK:	ROR FRBIT(R3)	;Set FRBIT to next item.
	BIT FRBIT(R3),MASK(R3) ;Is this item available?
	BNE GDBLK		;No.  Try again.
	BIS FRBIT(R3),MASK(R3) ;Yes.  Set mask appropriately.
	MOV R3,R2	;
	ADD #WORD0,R2	;R2 ← LOC[first item in block]
	MOV FRBIT(R3),R3;R3 ← FRBIT.  We are about to calculate address of item.
	BMI GT3		;If R3 has 15 bit on, then R2 is right.
GT4:	ADD R0,R2	;Else R2 ← LOC[next item in block]
	ROL R3		;
	BPL GT4		;Try again.
GT3:	MOV R2,R0	;Almost done.  R0 ← LOC[found item]
GTRET:	MOV (SP)+,R3	;Restore R3
	MOV (SP)+,R2	;Restore R2
	RTS PC		;Done.